package lib

func init() {
	Probs = append(Probs, Problem{
		Num:         98,
		Discription: "字符串s1 s2是否能形成交错字符串s3",
		Level:       2,
		Labels: map[string]int{
			"动态规划": 1,
			"字符串":  1,
			"空间复用": 1,
		},
	})
}

func IsInterleave(s1 string, s2 string, s3 string) bool {
	m := len(s1)
	n := len(s2)
	if m+n != len(s3) {
		return false
	}

	//dp[i][j]表示s1[:i]和s2[:j]是否能构成s3[:i+j]的交叉字符串
	//dp[j]表示i为某个值时，s1[:i]和s2[:j]是否能构成s3[:i+j]的交叉字符串
	dp := make([]bool, n+1)
	//初始化第一行
	dp[0] = true
	for j := 1; j <= n; j++ {
		dp[j] = dp[j-1] && s3[j-1] == s2[j-1]
	}

	for i := 1; i <= m; i++ {
		//每换一行初始化第一列
		dp[0] = dp[0] && s3[i-1] == s1[i-1]

		for j := 1; j <= n; j++ {
			pos := i + j - 1
			//dp[j]初始时值为dp[i-1][j]
			//如果s3[pos] != s1[i-1],先置为false，因为dp[j]初始时值可能为true
			if s3[pos] != s1[i-1] {
				dp[j] = false
			}

			//如果s3[pos] == s2[j-1]，dp[j]可以选择和dp[j-1]一样
			if s3[pos] == s2[j-1] {
				dp[j] = dp[j] || dp[j-1]
			}
		}
	}

	return dp[n]
}
